package com.south.base.test.arithmetic;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。
 * 你需要给出所有可能的组合的结果。
 * 有效的运算符号包含 +, - 以及 * 。
 *
 * @author Administrator
 * @date 2019/6/20 16:19
 */
public class DiffWaysToCalc {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> list = new ArrayList<>();
        int len = input.length();
        char[] chars = input.toCharArray();
        for (int i = 0; i < len; i++) {
            char c = chars[i];
            if (c != '+' && c != '-' && c != '*') {
                continue;
            }
            // 出现运算符号，递归求解前半段和后半段。
            List<Integer> left = diffWaysToCompute(new String(chars, 0, i));
            List<Integer> right = diffWaysToCompute(new String(chars, i + 1, len - 1 - i));
            for (int l : left) {
                for (int r : right) {
                    switch (c) {
                        case '+':
                            list.add(l + r);
                            break;
                        case '-':
                            list.add(l - r);
                            break;
                        case '*':
                            list.add(l * r);
                            break;
                    }
                }
            }
        }
        if (list.size() == 0) {
            list.add(Integer.valueOf(input));
        }
        return list;
    }

    @Test
    public void test() {
        System.out.println(diffWaysToCompute("2-1-1-1"));
    }
}